We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It is known that, for the Lebesgue measure $d\mu(x) = dx$, one may show an error bound $O(1/\sqrt{r})$ if $h$ is a sum-of-squares density, and an $O(1/r)$ error bound if $h$ is the density of a beta distribution. In this paper, we show an error bound of $O(1/r^2)$, if $d\mu(x) = \left( \prod_{i=1}^n \sqrt{1-x_i^2} \right)^{-1}$ (the well-known measure in the study of orthogonal polynomials), and $h$ has a Schmüdgen-type representation with respect to $[-1,1]^n$, which is a more general condition than a sum of squares. The convergence rate analysis relies on the theory of polynomial kernels and, in particular, on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eigenvalue problems, as is also the case for sum-of-squares densities.
展开▼
机译:我们考虑在超立方体$ [-1,1] ^ n $上最小化给定的$ n $变量多项式$ f $的问题。 Lasserre提出的一个想法是,在多项式密度函数$ h $(给定度数$ r $)上找到$ [-1,1] ^ n $的概率分布,该分布使期望值$ \ int _ {[-1, 1] ^ n} f(x)h(x)d \ mu(x)$,其中$ d \ mu(x)$是$ [-1,1] ^ n $支持的固定有限Borel度量。众所周知,对于Lebesgue度量$ d \ mu(x)= dx $,如果$ h $是平方和密度,则可能会显示出一个误差范围$ O(1 / \ sqrt {r})$ ,如果$ h $是Beta分布的密度,则错误界限为$ O(1 / r)$。在本文中,如果$ d \ mu(x)= \ left(\ prod_ {i = 1} ^ n \ sqrt {1-x_i ^ 2 } \ right)^ {-1} $(正交多项式研究中的众所周知的度量),并且$ h $具有关于$ [-1,1] ^ n $的Schmüdgen类型表示,即比平方和更一般的条件。收敛速度分析依赖于多项式核的理论,尤其是杰克逊核。我们还表明,所得的上限可以计算为广义特征值问题,平方和密度的情况也是如此。
展开▼